package org.basis.algorithm.promote;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * 滑动窗口内的最大值问题
 * 【题目】
 * 有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次 向右边滑 一个位置。
 * 例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时:
 * [4 3 5]4 3 3 6 7
 * 4[3 5 4]3 3 6 7
 * 4 3[5 4 3]3 6 7
 * 4 3 5[4 3 3]6 7
 * 4 3 5 4[3 3 6]7
 * 4 3 5 4 3[3 6 7]
 * 窗口中最大值为5
 * 窗口中最大值为5
 * 窗口中最大值为5
 * 窗口中最大值为4
 * 窗口中最大值为6
 * 窗口中最大值为7
 * 如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。
 * 请实现一个函数。
 * 输入:整型数组arr，窗口大小为w。
 * 输出:一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的 以本题为例，结果应该 返回{5,5,5,4,6,7}。
 *
 * @author Mr_wenpan@163.com 2022/01/06 16:06
 */
public class SlidingWindowMaxArray {

    public static void main(String[] args) {
        int[] ints = new int[]{1, 2, 3, 4, 5, 6};
        int[] maxWindow = getMaxWindow1(ints, 3);
        int[] mw = getMaxWindow(ints, 3);

        for (int value : maxWindow) {
            System.out.print(value + "   ");
        }

        System.out.println();

        for (int i = 0; i < maxWindow.length; i++) {
            System.out.print(mw[i] + "   ");
        }

        boolean res = isContains("abcdefghijk", "ijk");
        System.out.println(res);
    }

    /**
     * 使用O（N）复杂度来求解窗口最大值问题
     */
    public static int[] getMaxWindowx(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        int index = 0;
        int[] res = new int[arr.length - w + 1];
        // 定义一个单调递增的队列
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            // 如果队列中最后一个位置的元素对应的数字小于当前数字，则将前面的丢弃
            while (!queue.isEmpty() && arr[queue.peekLast()] <= arr[i]) {
                queue.pollLast();
            }
            // 将当前下标加入队列
            queue.addLast(i);
            // 窗口向右移动一个位置后，如果队头的元素正好是最左窗口位置（无效位置），则将他移除
            if (queue.peekFirst() == (i - w)) {
                queue.pollFirst();
            }
            // 到达窗口长度后
            if (i >= w - 1) {
                res[index++] = arr[queue.peekFirst()];
            }
        }

        return res;
    }

    /**
     * 使用O（N）复杂度来求解窗口最大值问题
     */
    public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        // 单调递减的队列
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;

        // 窗口每次右移一个位置，如果窗口的大小达到了指定的长度w，那么就开始统计窗口内的最大值
        for (int i = 0; i < arr.length; i++) {
            // 如果此时队列里有元素，且排在最后的元素比当前元素小，那么就将他取出，一直到遇到比自己大的元素为止
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
                qmax.pollLast();
            }
            // 将i位置加入
            qmax.addLast(i);
            // 过期的位置是队列头元素所代表的下标
            // i - w 表示窗口右移时过期的位置，如果过期的位置是链表头元素代表的下标，则直接将这个头移除
            // 这里 i - w 由于 i 的不断增大，所以 i - w 也不断增大，所以i - w 就表示窗口右移一个单位
            if (qmax.peekFirst() == i - w) {
                qmax.pollFirst();
            }
            // 窗口形成了，那么就开始统计窗口内的最大值了
            if (i >= w - 1) {
                // 窗口内的最大值其实就是队列中的头元素对应的节点
                res[index++] = arr[qmax.peekFirst()];
            }
        }

        return res;
    }

    public static int[] getMaxWindowTest(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }

        // 定义一个单调递减的双端队列
        LinkedList<Integer> queue = new LinkedList<>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;

        // i 每增大1就表示窗口往右移1
        for (int i = 0; i < arr.length; i++) {
            // 如果前面的数字比当前位置的数字小那么就依次弹出，知道不比arr[i] 小为止
            while (!queue.isEmpty() && arr[queue.peekLast()] <= arr[i]) {
                // 弹出队列尾部节点
                queue.pollLast();
            }
            // 将i位置加入到队列尾部
            queue.addLast(i);

            // 窗口向右滑动一个，判断过期位置是否是队列头元素代表的位置
            // i - w 表示窗口左边界
            if (queue.peekFirst() == i - w) {
                // 如果过期位置是队列头位置，那就将队列头位置丢弃
                queue.pollFirst();
            }
            // 队列头元素代表的就是当前窗口内的最大值
            // 如果窗口达到长度
            if (i >= w - 1) {
                res[index++] = queue.peekFirst();
            }
        }

        return res;
    }

    /**
     * 经典的窗口问题，时间复杂度O（N * M）
     */
    public static int[] getMaxWindow1(int[] arr, int w) {
        if (arr == null || arr.length < 1 || arr.length < w) {
            return new int[0];
        }
        int index = 0;
        ArrayList<Integer> res = new ArrayList<>();
        // 从0位置开始走，直到最后一个窗口，依次找每个窗口内的最大值
        for (int i = 0; i <= arr.length - w; i++) {
            index = i;
            int max = arr[i];
            // 寻找当前窗口内的最大值
            while (index < i + w) {
                max = Math.max(arr[index], max);
                index++;
            }
            // 记录窗口内的最大值
            res.add(max);
        }
        int[] ints = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ints[i] = res.get(i);
        }
        return ints;
    }

    /**
     * 使用滑动窗口来判断str1是否包含str2
     */
    public static boolean isContains(String str1, String str2) {

        if (str1 == null || str2 == null || str1.length() < str2.length()) {
            return false;
        }

        // 这里可以直接使用系统提供的函数，但是没必要。系统提供的函数肯定效率比这种经典窗口问题效率高，因为他是使用了类似KMP算法优化过的
//        return str1.contains(str2);

        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();

        int idx1 = 0;
        int idx2 = 0;

        // 从第0个位置起依次比较子串是否等于str2
        for (int i = 0; i < chars1.length; i++) {
            idx1 = i;
            idx2 = 0;
            // idx1和idx2都不越界，并且相等才继续走，否则退出
            while (idx2 < chars2.length && idx1 < chars1.length && chars1[idx1] == chars2[idx2]) {
                idx1++;
                idx2++;
            }

            // 判断从i位置起，是否有完全匹配str2
            if (idx2 == str2.length()) {
                return true;
            }
        }
        return false;
    }

}
